#include <assert.h>
#include <stdio.h>

#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;


struct Token {  
  bool is_terminal;
  string name;
  
  inline Token() : is_terminal(false), name("") {}
  inline Token(bool in_is_terminal, const string &in_name) 
    : is_terminal(in_is_terminal), name(in_name) {}
};

inline bool operator==(const Token &a, const Token &b) {
  return a.is_terminal == b.is_terminal && a.name == b.name;
}

inline bool operator!=(const Token &a, const Token &b) {
  return !(a == b);
}


class Exception {};


// A rule, like S -> foo bar etc
typedef vector<Token> TableRule;
typedef map<string, TableRule*> TableRow;

struct ParsingTable {
  Token start_symbol;
  map<string, TableRow> table;
};

ParsingTable read_parsing_table(istream &in) {
  ParsingTable pt;
  
  while (in) {
    
    TableRule *rule = new TableRule();
    
    string line;
    getline(in, line);
    if (line == "")
      continue;
    
    istringstream iss(line);
    string nonterminal_name, terminal_name, s;
    iss >> nonterminal_name;
    iss >> terminal_name;
    iss >> s;
    
    if (pt.start_symbol.name == "") {
      pt.start_symbol = Token(false, nonterminal_name);
      cout << "start symbol is: " << nonterminal_name << endl;
    }
    
    if (terminal_name == "{EPSILON}")
      terminal_name = "$";
    
    cout << "read parsing table cell: " << nonterminal_name << " " << terminal_name << " " << s << endl;
    
    assert(s == ":");

    pt.table[nonterminal_name][terminal_name] = rule;
  
    
    iss >> s;
    while (iss) {
      // TerminalType tt = TerminalType::find(terminal);
      cout << "rule token: '" << s << "'" << endl;
      assert(s != "");
      
      // Create a token. It's a terminal if it doesn't start with '<'.
      if (s != "{EPSILON}")
        rule->push_back(Token(s[0] != '<', s));
      iss >> s;
    }

  }
  
  return pt;
}

deque<string> read_tokens(istream &in) {
  deque<string> tokens;
  string s;
  
  in >> s;
  while (in) {
    cout << "Token: " << s << endl;
    tokens.push_back(s);
    in >> s;
  }
  
  tokens.push_back("$");
   
  return tokens;
}

static Token STACK_BOTTOM(true, "$");

int main(int argc, const char **argv) {
  
  if (argc != 3) {
    cout << "usage: driver parse_table.pt tokens.tok" << endl;
    return 1;
  }
  
  cout << "Reading parse table from " << argv[1] << " and tokens from " << argv[2] << "." << endl;
  
  ifstream parse_table_in(argv[1]);
  ifstream tokens_in(argv[2]);
  
  if (!parse_table_in.is_open()) {
    cout << "Error: " << argv[1] << ": cannot read." << endl;
    return 1;
  }
  
  if (!tokens_in.is_open()) {
    cout << "Error: " << argv[2] << ": cannot read." << endl;
    return 1;
  }
  
  ParsingTable pt = read_parsing_table(parse_table_in);
  deque<string> input = read_tokens(tokens_in);
  
  vector<Token> stack;
  
  stack.push_back(STACK_BOTTOM);
  stack.push_back(pt.start_symbol);
  // push start symbol.
  
  try {
    while (input.size() && stack.back() != STACK_BOTTOM) {

      cout << "processing: input: " << input.front() << "; top of stack: " << stack.back().name << endl;

      if (stack.back().is_terminal && input.front() == stack.back().name) {
        // Match.
        cout << "Match " << endl;
        stack.pop_back();
        input.pop_front();
      } else if (!stack.back().is_terminal) {
        // Generate
        cout << "Generate: " << stack.back().name << ", " << input.front() << ": pushing tokens [";
        TableRule *rule = pt.table[stack.back().name][input.front()];
        if (rule == NULL) {
          // Error.
          cout << "Error: no rule for N[" << stack.back().name << "][" << input.front() << "]" << endl;
          throw Exception();
        }
        stack.pop_back();
        for (vector<Token>::reverse_iterator it = rule->rbegin(); it != rule->rend(); it++) {
          cout << " " << it->name;
          stack.push_back(*it);
        }
        cout << "]" << endl;
      } else {
        // Error.
        cout << "Error: can neither match nor generate. " << endl;
        throw Exception();
      }
    }

    if (input.size() == 1 && stack.back() == STACK_BOTTOM && input.back() == "$") {
      cout << "Accept" << endl;
    } else {
      cout << "Reject." << endl;
      throw Exception();
    }
  } catch (const Exception &goodintentions) {
    cout << "Error. Stack:";
    for (size_t i = 0; i < stack.size(); i++)
      cout << " " << stack.at(i).name;
    cout << endl;
    if (!input.empty())
      cout << "Current token: " << input.back() << endl;
    else
      cout << "Current token: (nothing)" << endl;
    return 1;
  }

  // TODO - delete the TableRules in the ParsingTable.
  
  return 0;
  
}
